function heapSort (nums: number[]) {
  buildHeap(nums)

  for (let i = nums.length - 1; i >= 0; i--) {
    [nums[0], nums[i]] = [nums[i], nums[0]]
    maxHeap(nums, 0, i)
  }
  console.log(nums)
}

function buildHeap (nums: number[]) {
  const n: number = nums.length
  const height: number = n >> 1
  for (let i = height - 1; i >= 0; i --) {
    maxHeap(nums, i, nums.length)
  }
}
function maxHeap (nums: number[], i: number, heapsize: number) {
  let largestIndex: number = i
  let leftIndex: number = 2 * i + 1
  let rightIndex: number = leftIndex + 1
  if (leftIndex < heapsize && nums[leftIndex] > nums[largestIndex]) {
    largestIndex = leftIndex
  }
  if (rightIndex < heapsize && nums[rightIndex] > nums[largestIndex]) {
    largestIndex = rightIndex
  }
  if (largestIndex !== i) {
    [nums[i], nums[largestIndex]] = [nums[largestIndex], nums[i]]
    maxHeap(nums, largestIndex, heapsize)
  }
}

heapSort([7, 4, 5, 1, 3, 6, 8, 2])